package job.meituan;

import java.util.*;

/**
 * Author: Zhang Dongwei
 * Date: 2023/8/12 16:03
 * 小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。
 * 小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。
 * 小美想知道，自己最多可以染红多少个节点？
 * 输入描述
 * 第一行输入一个正整数n，代表节点的数量。第二行输入n个正整数ai，代表每个节点的权值。接下来的n-1行，每行输入两个正整数u，v，代表节点u和节点v有一条边连接。
 * 输出描述
 * 输出一个整数，表示最多可以染红的节点数量。

 * 示例1
 * 输入
 * 3
 * 3 3 12
 * 1 2
 * 2 3
 * 输出
 * 2
 *
 * 说明：
 * 可以染红第二个和第三个节点。
 * 请注意，此时不能再染红第一个和第二个节点，因为第二个节点已经被染红。
 * 因此，最多染红 2 个节点。
 *
 * 思路与代码
 * 树形dp。
 * 每个节点可以染色或者不染色。
 * 染色的话，则必须找到一个可以染色的孩子，其他节点不可以染色。
 * 不染色的话，则孩子染色和不染色都可以，取最大值即可。
 */
public class mt5 {
    public static void main(String[] args) {
        new mt5().solve();
    }

    int n;
    int[] v;
    List<List<Integer>> graph = new ArrayList<>();
    void solve() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        v = new int[n+1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
        }
        for (int i = 0; i <= n; i++) graph.add(new LinkedList<>());

        int res = 0;
        for (int i = 0 ; i < n  - 1; i ++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        dp = new int[n+1][2];
        dfs(1,-1);
        System.out.println(Math.max(dp[1][0], dp[1][1]));
    }

    int[][] dp; //node 0不染色 1染色

    void dfs(int node, int pre) {
        for (int next : graph.get(node)) {
            if (next != pre) {
                dfs(next,node);
            }
        }

        if (graph.get(node).size() == 0 && graph.get(node).get(0) == pre) {
            dp[node][1] = 1;
        }

        //不染色
        int tmp = 0;
        for (int next : graph.get(node)) {
            if (next != pre) {
                dp[node][0] += Math.max(dp[next][0], dp[next][1]) ;
                tmp += dp[next][0];
            }
        }

        for (int next : graph.get(node)) {
            if (next != pre) {
                if (isAns(v[next], v[node])) dp[node][1] = Math.max(dp[node][0] - Math.max(dp[next][0], dp[next][1])+2+dp[next][0], dp[node][1]);
            }
        }
    }

    boolean isAns(int a, int b) {
        if (a < 0 || b < 0) return false;
        long c = a*b;
        int sq = (int) Math.sqrt(c);
        return sq*sq == c;
    }
}
